package developer.算法.子串.最小覆盖子串;

public class Other {
    public static void main(String[] args) {
        Solution solution = new Solution();
    }

  static   class Solution {
        public String minWindow(String S, String t) {
            char[] s = S.toCharArray();
            int m = s.length;
            int ansLeft = -1;
            int ansRight = m;
            int[] cntS = new int[128]; // s 子串字母的出现次数
            int[] cntT = new int[128]; // t 中字母的出现次数
            for (char c : t.toCharArray()) {
                cntT[c]++;
            }

            int left = 0;
            for (int right = 0; right < m; right++) { // 移动子串右端点
                cntS[s[right]]++; // 右端点字母移入子串
                while (isCovered(cntS, cntT)) { // 涵盖
                    if (right - left < ansRight - ansLeft) { // 找到更短的子串
                        ansLeft = left; // 记录此时的左右端点
                        ansRight = right;
                    }
                    cntS[s[left]]--; // 左端点字母移出子串
                    left++;
                }
            }
            return ansLeft < 0 ? "" : S.substring(ansLeft, ansRight + 1);
        }

        private boolean isCovered(int[] cntS, int[] cntT) {
            for (int i = 'A'; i <= 'Z'; i++) {
                if (cntS[i] < cntT[i]) {
                    return false;
                }
            }
            for (int i = 'a'; i <= 'z'; i++) {
                if (cntS[i] < cntT[i]) {
                    return false;
                }
            }
            return true;
        }
    }

    static class SolutionB {
        public String minWindow(String S, String t) {
            char[] s = S.toCharArray();
            int m = s.length;
            int ansLeft = -1;
            int ansRight = m;
            int[] cnt = new int[128];
            int less = 0;
            for (char c : t.toCharArray()) {
                if (cnt[c] == 0) {
                    less++; // 有 less 种字母的出现次数 < t 中的字母出现次数
                }
                cnt[c]++;
            }

            int left = 0;
            for (int right = 0; right < m; right++) { // 移动子串右端点
                char c = s[right]; // 右端点字母
                cnt[c]--; // 右端点字母移入子串
                if (cnt[c] == 0) {
                    // 原来窗口内 c 的出现次数比 t 的少，现在一样多
                    less--;
                }
                while (less == 0) { // 涵盖：所有字母的出现次数都是 >=
                    if (right - left < ansRight - ansLeft) { // 找到更短的子串
                        ansLeft = left; // 记录此时的左右端点
                        ansRight = right;
                    }
                    char x = s[left]; // 左端点字母
                    if (cnt[x] == 0) {
                        // x 移出窗口之前，检查出现次数，
                        // 如果窗口内 x 的出现次数和 t 一样，
                        // 那么 x 移出窗口后，窗口内 x 的出现次数比 t 的少
                        less++;
                    }
                    cnt[x]++; // 左端点字母移出子串
                    left++;
                }
            }
            return ansLeft < 0 ? "" : S.substring(ansLeft, ansRight + 1);
        }
    }



}
